package com.leetcode.根据数据结构分类.栈;

import java.util.Stack;

/**
 * @author: ZhouBert
 * @date: 2020/11/20
 * @description: https://leetcode-cn.com/problems/valid-parentheses/
 */
public class A_20_有效的括号 {


	/**
	 * 给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串
	 * 1.左派入栈；
	 * 2.右派出栈；
	 * 但是匹配的方法写起来很麻烦
	 * [optimize]--> 利用 HashMap
	 *
	 * @param s
	 * @return
	 */
	public boolean isValid(String s) {
		char[] chars = s.toCharArray();
		Stack<Character> stack = new Stack<>();
		for (int i = 0; i < chars.length; i++) {
			if (chars[i] == '(' || chars[i] == '[' || chars[i] == '{') {
				stack.push(chars[i]);
			} else {
				if (stack.isEmpty()) {
					return false;
				}
				//如果是右派，就peek 比较
				//--> 可以优化一下，直接弹出来进行比较，而不用 peek
				if ((chars[i] == ')' && stack.peek() == '(') || (chars[i] == ']' && stack.peek() == '[') || (chars[i] == '}' && stack.peek() == '{')) {
					stack.pop();
				} else {
					return false;
				}
			}
		}
		if (stack.isEmpty()) {
			return true;
		} else {
			return false;
		}
	}


	/**
	 * 从大局观来看，比较简单的写法
	 * 但是贼耗时，字符串的查找和替换都是非常耗时的
	 * @param s
	 * @return
	 */
	public static boolean isValid2(String s) {
		int num = s.length() >> 1;
		for (int i = 0; i < num; i++) {
			s = s.replace("()", "");
			s = s.replace("[]", "");
			s = s.replace("{}", "");
		}
		return s.isEmpty();
	}

	public static void main(String[] args) {
		String s = "()";
		boolean res = isValid2(s);
	}
}
